#!/usr/bin/python
import sys

#aca se puede ver los lugares a los que se puede saltar desde 
#la o, las x son los saltos posibles con 1 salto.
#| |x| |x| |
#|x| | | |x|
#| | |o| | |
#|x| | | |x|
#| |x| |x| |
#quiero saltar desde (x,y) a (w,z), el tablero tiene nXx y matriz es la tabla dinamica
recorridoCount = 0
def cantidadDeSaltos(x,y,w,z,n,m):

	global matriz, recorrido, recorridoCount

	print "|%s|%s|" % (x,y)
	if recorrido[ (x*n) + y ] == 0:
		print "aumento %s %s %s " % (x,y,recorridoCount)
		recorridoCount += 1
		recorrido[ (x*n) + y ] = recorridoCount

	if w > n-1 or z > n-1 or w < 0 or z < 0:
		print "no encuentro"
		return -1

	vecinos = [(-2,-1),(-2,1),\
		(-1,-2),(-1,2),\
		(1,-2),(1,2),\
		(2,-1),(2,1)]

	(p,q) = (abs(w-x),abs(z-y))
	if (p,q) in matriz:
		print "encuentro en matriz (%s,%s) -> %s" % (p,q,matriz[(p,q)]) 
		return matriz[(p,q)]
	
	if p == 0 and q == 0:
		print "llege "
		return 0
	if (p,q) in vecinos:
		print "es un vecino"
		matriz[(p,q)] = 1
		return 1
	
	ret = -1 
	for t in vecinos:
		(p,q) = t
		#verifico que se pueda saltar a ese vecino
		if p+x >= 0 and q+y >= 0 and p+x < n and q+y < n and recorrido[ ((p+x)*n) + (q+y) ] == 0:
			print "llamo recursivo desde (%s,%s,%s,%s)" % (p+x,q+y,w,z)			
			saltos = cantidadDeSaltos(p+x,q+y,w,z,n,matriz)
			if saltos >= 0 and (ret == -1 or saltos+1 < ret ):
				ret = saltos+1
	if ret != -1:
			matriz[(abs(w-x),abs(z-y))] = ret

	print "de (%s,%s) a (%s,%s) se llega con %s saltos " % (x,y,w,z,ret)
	return ret

# la matriz la pienso tomando solo 1 cuarto del grafico
# que esta arriba con la o y las x.
# Si estoy en la o con saber como saltar al cuadrante derecho superior
# me alcanza para moverme en cualquier direccion
matriz = dict([ ((0,0) , 0 )])
n = 5
recorrido = [0] * (n * n)
resultado = cantidadDeSaltos(0,4,2,4,5,matriz)
print "fin %s" % resultado
print "-------------------------------------------------"
resultado = cantidadDeSaltos(0,4,0,3,5,matriz)
print "fin %s" % resultado
print "recorrido"
print "-------------------------------------------------"
resultado = cantidadDeSaltos(0,0,4,0,5,matriz)
print "fin %s" % resultado
print "recorrido"

for i in range(n):
	for j in range(n):
		sys.stdout.write( "%-3s " %  recorrido[i*n+j] )
	sys.stdout.write( "\n")
sys.stdout.write( "\n")

for k,v in  matriz.iteritems():
	print "%s => %s" % (k,v)